class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求二叉树的右视图
     * @param xianxu int整型vector 先序遍历
     * @param zhongxu int整型vector 中序遍历
     * @return int整型vector
     */
//     struct TreeNode {
//      int val;
//      TreeNode *left;
//       TreeNode *right;
//       TreeNode(int x) : val(x), left(NULL), right(NULL) {}
//   };
    unordered_map<int, int> hash;
    vector<int> solve(vector<int>& pre, vector<int>& vin) {
        // write code here
         vector<int>ans;
        int len=pre.size();
        if(len==0)
            return ans;
        for(int i=0;i<len;i++) hash[vin[i]]=i;
//先建树
        auto root=dfs(pre, vin, 0, len-1, 0, len-1);
       //采用层次遍历的方式，每遍历一层就把最右边的元素放入容器中
        list<TreeNode*>mylist;
        mylist.push_back(root);
        int count=1;
        while(!mylist.empty())
        {
            for(int i=0;i<count;i++)
            {
                if(mylist.front()->left) mylist.push_back(mylist.front()->left);
                if(mylist.front()->right) mylist.push_back(mylist.front()->right);
                if(i+1==count)
                    ans.push_back(mylist.front()->val);
                mylist.pop_front();
            }
            count=mylist.size();
        }
        return ans;
    }
    TreeNode* dfs(vector<int>&pre,vector<int>&vin,int pl,int pr,int vl,int vr)
    {
        if(pl>pr)
            return nullptr;
        TreeNode*root=new TreeNode(pre[pl]);
        int leftlen=hash[pre[pl]]-vl;
        root->left=dfs(pre,vin,pl+1,pl+leftlen,vl,vl+leftlen-1);
        root->right=dfs(pre,vin,pl+leftlen+1,pr,vl+leftlen+1,vr);
        return root;
    }
};